'''
	冒泡排序（是内排序）
	时间复杂度：最好:O(n)  平均:O(n^2) 最坏:O(n^2)
	稳定性：稳定
	空间复杂度：O(1)
	复杂性：简单
	基本思想：相邻的两个数进行比较，把小的数换到前面
'''
import time
from tool import swp, arr, arr_100, random_num

def BubbleSort(arr):
	if arr == None or len(arr) == 0:
		return 0
	i = 0
	while i < len(arr):
		j = len(arr) - 1
		while j > 0:
			if arr[j] < arr[j-1]:
				swp(arr, j, j-1)
			j = j - 1
		i = i + 1
	return arr

def Bubble_sort(arr):
	if arr == None or len(arr) == 0:
		return 0
	j = 0
	while j < len(arr):
		i = 0
		while i < (len(arr) -1 - j):
			if arr[i] > arr[i+1]:
				swp(arr, i, i+1)
			i = i + 1
		j = j + 1
	return arr

if __name__ == '__main__':
	# arr1 = random_num(2000)
	start = time.clock()
	arr = BubbleSort(arr_100)
	# arr = Bubble_sort(arr_100)
	end = time.clock()
	print(arr)
	print(end - start)

